class Solution
{
public:
    string smallestBeautifulString(string s, int k)
    {
        int n = s.length();
        int pos = n - 1;
        ++s[pos];
        while (pos >= 0 && pos < n)
        {
            if (s[pos] == k + 'a')
            {
                if (pos == 0)
                {
                    return "";
                }
                s[pos] = 'a';
                --pos;
                ++s[pos];
            }
            else if ((pos >= 1 && s[pos] == s[pos - 1]) || (pos >= 2 && s[pos] == s[pos - 2]))
            {
                ++s[pos];
            }
            else
            {
                ++pos;
            }
        }
        return s;
    }
};